Generate Parentheses
Leetcode #22 | Medium | Backtracking
Идея
Бектрекинг
Если можно добавить открытую скобку - пытаемся, если открытых больше чем закрытых - можно попытаться добавить закрытую. Добавление через StringBuilder
Big-O
- Время
O(C_n) - Память
O(N)
C_n - n-ое число Каталана
Код
class Solution {
private List<String> res = new ArrayList<>();
public List<String> generateParenthesis(int n) {
backtrack(new StringBuilder(), 0, 0, n);
return res;
}
private void backtrack(StringBuilder sb, int open, int close, int n) {
if (sb.length() == 2 * n) { res.add(sb.toString()); return; }
if (open < n) {
sb.append("("); backtrack(sb, open + 1, close, n); sb.deleteCharAt(sb.length() - 1);
}
if (close < open) {
sb.append(")"); backtrack(sb, open, close + 1, n); sb.deleteCharAt(sb.length() - 1);
}
}
}